package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 别以为你看过好多遍就是会了
 *
 * 最后捅死你的都是熟人
 * 杀你的都是熟人
 *
 * */
public class _236_low_c_a {
    
    /**
     * 做不出来，有罪吗？
     * */
    class ss {
        /*
         * 解法只有一种
         * 有一个辅助方法，返回一个节点或 null：如果某个节点是根，返回它；如果某个节点在根的左，或右，也返回它
         * 辅助方法返回后，判断返回值：如果俩 null，不太可能；一个根，就是它了；分居两侧，返回 root
         *
         * 我在想：我是一次判断一个还是一下判断两个？我这个辅助方法？
         *
         * 还在死记硬背，算了，标记为不会做
         * */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return null;
        }
    
        TreeNode dfs(TreeNode root, TreeNode left, TreeNode right) {
            if (left == root) return left;
            if (right == root) return right;
        
            return null;
        }
    }
    
    class lufei {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == root || q == root) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left != null) return left;
            return right;
        }
    }
    
    class official1 {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            dfs(root, p, q);
            return res;
        }
        TreeNode res;
        boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return false;
            if (q == root || p == root) {
                res = root;
                return true;
            }
            boolean left = dfs(root.left, p, q);
            boolean right = dfs(root.right, p, q);
            if (left && right) {
                res = root;
                return true;
            }
            return left || right;
        }
    
    }
    
    /**
    * 由于节点各不相同，故可以用这个方式
    * */
    class official2 {
        
        Map<Integer, TreeNode> parents = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root);
            while (p != null) {
                visited.add(p.val);
                p = parents.get(p.val);
            }
            while (q != null) {
                if (visited.contains(q.val))
                    return q;
                q = parents.get(q.val);
            }
            return null;
        }
        void dfs(TreeNode root) {
            if (root == null) return;
            TreeNode p = root.left;
            if (p != null) {
                parents.put(p.val, root);
                dfs(p);
            }
            p = root.right;
            if (p != null) {
                parents.put(p.val, root);
                dfs(p);
            }
        }
        
    }
    
}
